package com.example.algorithm.sort.shell;

import com.example.algorithm.sort.BaseSort;

/**
 * @program: algorithm
 * @description: 希尔排序
 * @packagename: com.example.algorithm.sort.shell
 * @author: Jay
 * @date: 2022/03/25 14:48:03
 **/
public class Shell extends BaseSort {

    public static void sort(Comparable[] a){
        //1.根据数组a的长度，确定增长量h的初始值
        int h = 1;
        while (h < a.length/2){
            h = 2*h + 1;
        }
        //2.希尔排序
        while (h >= 1){
            //排序
            //2.1找到待插入的元素
            for (int i = h; i < a.length; i++){
                //2.2把待插入的元素插入到有序数列中
                for (int j = i; j >= h; j-=h ){
                    //待插入的元素是a[j] ,比较a[j-h]
                    if (greater(a[j-h],a[j])){
                        exch(a,j,j-h);
                    }else {
                        //结束循环
                        break;
                    }
                }
            }

            //减小h的值
            h = h/2;
        }
    }
}
